1. Field of the Invention
The present invention relates to wireless sensor networks, and particularly to a recursive time synchronization protocol (RTSP) method for wireless sensor networks (WSNs) that efficiently synchronizes the nodes of a wireless sensor network.
2. Description of the Related Art
Wireless Sensor Networks (WSNs) require accurate time synchronization (usually less than one microsecond) for many reasons, such as precise time-stamping of messages, in-network signal processing, time-based localization, TDMA-based medium access, cooperative communication, coordinated actuation, and energy-efficient duty cycling of sensor nodes. There are several ways to achieve synchronization, which include ordering of events, local synchronization, global synchronization, etc. However, many applications need global time synchronization, which requires all nodes to be synchronized with one global clock.
As WSNs are commonly deployed for monitoring remote and hazardous environments, it is not feasible to recharge or replace the battery of sensor nodes. Therefore, sensor nodes should use their energy very efficiently, even when a power harvesting technique is used with a battery of limited capacity. It is important to note that most of the sensors' energy is consumed by message transmission and idle listening, and that clock synchronization algorithms work by exchanging messages among the nodes. Therefore, the lifetime of WSNs can be significantly prolonged by using an energy-efficient protocol for clock synchronization. However, the total energy consumed by a time-synchronization protocol depends on the re-synchronization interval, T, and the ratio of time-synchronization messages to the total number of messages in the network that is determined by the application.
The issue of clock synchronization has been investigated extensively, and several methods or protocols have been proposed for global time synchronization, such as GPS-based clock synchronization, Network Time Protocol (NTP), Precision Time Protocol (PTP), Reference Broadcast Synchronization (RBS), Timing-sync Protocol for Sensor Networks (TPSN), and Flooding Time Synchronization Protocol (FTSP).
The GPS-based clock-synchronization can provide an accuracy of 1 μs or better, but it is costly, energy-inefficient, and infeasible in obstructed environments. The NTP is commonly used in traditional computer networks, including the Internet, but it is not suitable for WSNs because of its very low accuracy (i.e., in the order of milliseconds only), high complexity and energy inefficiency. The PTP, defined by the IEEE 1588 standard, can achieve clock accuracy in the sub-microsecond range for networked measurement and control systems, but it is suitable only for a hierarchical master-slave architecture. The RBS uses receiver-receiver synchronization to produce an average accuracy of 29.1 us for a single hop network, but this accuracy is not sufficient for WSNs which require an accuracy of 1 μs or better. The TPSN uses sender-receiver synchronization and MAC-layer time-stamping of messages at the sender side to provide an average accuracy of 16.9 μs for a single hop network and less than 20 μs for multi-hop network, but it is still not sufficient for WSNs.
The Flooding Time Synchronization Protocol (FTSP) is the most commonly used protocol for clock synchronization in WSNs. It broadcasts messages with timing information from a single sender to several receivers without any exchange among themselves, and strives to tackle the flaws of TPSN. It dynamically elects a reference node, which regularly floods its current timestamp into the network, creating an ad-hoc tree structure of the network instead of a fixed spanning tree. The MAC-layer time-stamping at both sender and receiver sides eliminates all kind of random delays, except propagation delay. The timestamps are made at the end of each byte after the SFD (Start of Frame Delimiter) or SYNC byte, and are normalized, averaged, and error-corrected, and then the final timestamp is embedded into the message. A node waits for sufficient data points that are pairs of global and local timestamps, and then estimates the offset and skew using a least square linear regression (LSLR). Any node that is fully synchronized with the reference node begins flooding its own estimation of the global clock. In this way, the FTSP provides an accuracy of 1.48 μs for the single hop case, and about 0.5 μs per hop in a multi-hop network.
There have been many efforts to improve the FTSP in terms of accuracy, efficiency, energy consumption, etc. Exemplary related art includes improved accuracy and power consumption in a single hop network using a different method of time-stamping that is based on the Start of Frame Delimiter (SFD) byte. In the SFD-based time-stamping, messages are time-stamped using the time at which a radio chip generates an interrupt for the microcontroller after the SFD byte has been sent or received. Similarly, other related art obtains an accuracy of 0.4 us in a single hop network by using SFD-based time-stamping along with a Kalman-filter for skew estimation. Although the accuracy of FTSP and its improved versions is sufficiently good, the energy consumption is very high, and the distant nodes are poorly synchronized.
The present inventors proposed a Recursive Time Synchronization Protocol (RTSP) presented at the IEEE SAS2012 in Brescia, Italy, described in Muhammad Akhlaq and Tarek R. Sheltami, “The Recursive Time Synchronization Protocol for Wireless Sensor Networks”, 2012 IEEE Sensors Applications Symposium (SAS), Feb. 7-9, 2012, pages 1-6” which is incorporated by reference in its entirety herein. The RTSP provides an average accuracy of 0.3 μs per-hop in a large multi-hop flat network (i.e., without clustering), while using only ⅕th of the energy consumed by FTSP in the long run. However, the related art RTSP does not address the fact that WSNs are usually clustered and hierarchical.
Thus, a recursive time synchronization protocol method for wireless sensor networks solving the aforementioned problems is desired.